// https://leetcode-cn.com/problems/beautiful-array/submissions/
// https://blog.csdn.net/qq_17550379/article/details/83572902
// 我们如果有一个漂亮数组B，我们根据前面的性质知道2*B-1是一个漂亮数组并且是奇数数组，而2*B也是一个漂亮数组并且是偶数数组。那么我们通过2*B+2*B-1必然可以构成任意一个漂亮数组了。

class Solution {
public:
    vector<int> beautifulArray(int N) {
        // 法一：非递归写法
        // vector<int> result = {1};
        // while (result.size() < N)
        // {
        //     vector<int> tmp;
        //     for (auto i : result)
        //     {
        //         if (i*2 - 1 <= N) tmp.push_back(i*2 - 1);
        //     }
        //     for (auto i : result)
        //     {
        //         if (i*2 <= N) tmp.push_back(i*2);
        //     }
        //     result = tmp;
        // }
        // return result;
        
        // 法二：递归写法
        vector<int> result;
        if (N == 1) 
        {
            result.push_back(N);
            return result;
        }
        vector<int> odd = beautifulArray((N + 1) / 2);
        vector<int> even = beautifulArray(N / 2);
        for (int o: odd)
        {
            result.push_back(2 * o - 1);
        }
        for (int e: even)
        {
            result.push_back(2 * e);
        }
        return result;
    }    
};
